from typing import List


class SegmentTreeForMax:
    """求最小值线段树"""

    class _Node:
        """线段树结点"""
        __slots__ = "start", "end", "val", "left", "right", "lazy"

        def __init__(self, start, end):
            self.start = start  # 左侧边界（包含）
            self.end = end  # 右侧边界（包含）
            self.left = None  # 结点左子结点
            self.right = None  # 结点右子节点
            self.val = 0  # 当前结点最小值
            self.lazy = 0  # 懒惰计算标签（即未计算的子结点最小值）

    def __init__(self, size):
        """初始化线段树实例"""
        self.root = self._Node(0, size)

    def _update(self, node, pos1, pos2, data):
        """更新数据"""
        # 当前区间正好为当前结点的情况：即不需要继续分裂的情况
        if node.start == pos1 and node.end == pos2:
            node.val = max(node.val, data)
            node.lazy = max(node.lazy, data)

        # 当前区间为当前结点的部分的情况：即需要继续分裂的情况
        else:
            mid = (node.start + node.end) // 2

            # 创建两个子结点
            if node.left is None:
                node.left = self._Node(node.start, mid)
            if node.right is None:
                node.right = self._Node(mid + 1, node.end)

            # 下推当前结点的懒惰计算标签
            if node.lazy != 0:
                node.left.val = max(node.left.val, node.lazy)
                node.left.lazy = max(node.left.lazy, node.lazy)
                node.right.val = max(node.right.val, node.lazy)
                node.right.lazy = max(node.right.lazy, node.lazy)
                node.lazy = 0

            # 更新当前结点的子结点
            node.val = max(node.val, data)
            if pos2 <= mid:
                self._update(node.left, pos1, pos2, data)
            elif pos1 >= mid + 1:
                self._update(node.right, pos1, pos2, data)
            else:
                self._update(node.left, pos1, mid, data)
                self._update(node.right, mid + 1, pos2, data)

    def _query(self, node, start, end):
        """查询数据"""

        # 当前区间正好为当前结点的情况：即不需要继续分裂的情况
        if node.start == start and node.end == end:
            return node.val

        # 当前结点没有子结点的情况：即当前结点下所有位置的结果一致的情况
        elif node.left is None and node.right is None:
            return node.val

        # 当前区间为当前结点的部分的情况：即需要继续分裂的情况
        else:
            mid = (node.start + node.end) // 2

            # 创建两个子结点
            if node.left is None:
                node.left = self._Node(node.start, mid)
            if node.right is None:
                node.right = self._Node(mid + 1, node.end)

            # 下推当前结点的懒惰计算标签
            if node.lazy != 0:
                node.left.val = max(node.left.val, node.lazy)
                node.left.lazy = max(node.left.lazy, node.lazy)
                node.right.val = max(node.right.val, node.lazy)
                node.right.lazy = max(node.right.lazy, node.lazy)
                node.lazy = 0

            # 查询当前结果的最小值
            if end <= mid:
                return self._query(node.left, start, end)
            elif start >= mid + 1:
                return self._query(node.right, start, end)
            else:
                return max(self._query(node.left, start, mid),
                           self._query(node.right, mid + 1, end))

    def query_one(self, query):
        return self._query(self.root, query, query)

    def query_range(self, start, end):
        return self._query(self.root, start, end)

    def update_one(self, query, data):
        self._update(self.root, query, query, data)

    def update_range(self, start, end, data):
        self._update(self.root, start, end, data)


class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        size = 0
        for position in positions:
            size = max(size, position[0] + position[1] + 1)
        # print("构造范围:", size)

        st = SegmentTreeForMax(size)

        highest = 0
        ans = []
        for left, size in positions:
            h = st.query_range(left, left + size - 1) + size
            # print("Left:", left, "Right:", left + size - 1, "查询结果:", h - size, "更新结果:", h)
            st.update_range(left, left + size - 1, h)
            highest = max(highest, h)
            ans.append(highest)

        return ans


if __name__ == "__main__":
    # [2,5,5]
    print(Solution().fallingSquares([[1, 2], [2, 3], [6, 1]]))

    # [100, 100]
    print(Solution().fallingSquares([[100, 100], [200, 100]]))

    # 测试用例19/44 [1,10,18]
    print(Solution().fallingSquares([[2, 1], [2, 9], [1, 8]]))
